#include "sort.h"

#include<string.h>
#include<assert.h>
#include<malloc.h>
#include<stdlib.h>
#include<stdio.h>

void Print(int *a,int n)
{
  int i=0;
  for(;i<n;i++)
  {
    printf("%d ",a[i]);
  }
  printf("\n");
}

void swap(int *x,int *y)
{
  int temp=*x;
  *x=*y;
  *y=temp;
}

void BubbleSort(int *a,int n)
{
  int i,j;
  for(i=0;i<n-1;i++)
  {
    int ischange=0;
    for(j=0;j<n-i-1;j++)
    {
      if(a[j]>a[j+1])
      {
        swap(&a[j],&a[j+1]);
        ischange=1;
      }
    }
    if(!ischange)
    {
      return ;
    }
  }
}

// 三数取中法
int GetmiddleIndex(int *a,int left,int right)
{
    int mid = left+(right-left)/2;
    if(a[left]<a[right-1])
    {
      if(a[mid]<a[left])
      {
        return left;
      }
      else if(a[right-1]<a[mid])
      {
        return right-1;
      }
      else
      {
        return mid;
      }
    }
    else 
    {
      if(a[mid]<a[right-1])
      {
        return right-1;
      }
      else if(a[left]<a[mid])
      {
        return left;
      }
      else
      {
        return mid;
      }
    }
}

int PartSort1(int *a,int left,int right)
{
  int mid=GetmiddleIndex(a,left,right);
  int begin=left;
  int end=right-1;
  swap(&a[mid],&a[end]);
  int key = a[end];
  while(begin<end)
  {
    while(begin<end && a[begin]<= key)
    {
      begin++;
    }
    while(begin<end && a[end]>=key)
    {
      end--;
    }
    if(begin<end)
    {
      swap(&a[begin],&a[end]);
    }
  }
  if(begin!=right-1)
  {
    swap(&a[begin],&a[right-1]);
  }
  return begin;
}

int PartSort2(int *a,int left,int right)
{
  int begin=left;
  int end=right-1;
  int mid= GetmiddleIndex(a,left,right);
  swap(&a[mid],&a[end]);
  int key=a[end];

  while(begin<end)
  {
    while(begin<end && a[begin]<=key)
    {
      begin++;
    }
    if(begin!=end)
    {
      a[end]=a[begin];
      end--;
    }
    while(begin<end && a[end]>=key)
    {
      end--;
    }
    if(begin!=end)
    {
      a[begin]=a[end];
      begin++;
    }
  }
  a[begin] = key;
  return begin;
}

int PartSort3(int *a,int left,int right)
{
  int cur=left;
  int prev=cur-1;
  int mid=GetmiddleIndex(a,left,right);
  swap(&a[mid],&a[right-1]);

  int key=a[right-1];

  while(cur<right)
  {
    if(a[cur]<key && ++prev!=cur)
    {
      swap(&a[cur],&a[prev]);
    }
    ++cur;
  }

  if(++prev != right-1)
  {
    swap(&a[prev],&a[right-1]);
  }
  return prev;
}


void SelectSort(int *a,int n)
{
  int begin=0,end=n-1;
  while(begin<end)
  {
    int maxPos=begin;
    int minPos=begin;

    int index=begin+1;
    while(index <= end)
    {
      if(a[index]>a[maxPos]) maxPos=index;
      if(a[index]<a[minPos]) minPos=index;
      index++;
    }
    if(maxPos!=end)
    {
      swap(&a[maxPos],&a[end]);
    }
    if(minPos==end)
    {
      minPos=maxPos;
    }
    if(minPos!=begin)
    {
      swap(&a[minPos],&a[begin]);
    }
    begin++;
    end--;
  }
}

void AdjustDwon(int *a,int n,int root)
{
  int father=root;
  int child=father*2+1;
  while(child<n)
  {
    if(child+1<n && a[child]<a[child+1])
    {
      child+=1;
    }
    if(a[father]<a[child])
    {
      swap(&a[father],&a[child]);
      father=child;
      child=father*2+1;
    }
    else
    {
      return ;
    }
  }
}

void HeapSort(int *a,int n)
{
  int root=(n-2)/2;
  for(;root>=0;root--)
  {
    AdjustDwon(a,n,root);
  }

  int end=n-1;
  while(end>0)
  {
    swap(&a[0],&a[end]);
    AdjustDwon(a,end,0);
    end--;
  }
}

void InsertSort(int *a,int n)
{
  int i=1;
  for(;i<n;i++)
  {
    int key=a[i];
    int end=i-1;
    while(end>=0 && a[end]>key)
    {
      a[end+1]=a[end];
      end--;
    }
    a[end+1]=key;
  }
}

void ShellSort(int *a,int n)
{
  int gap=n;
  while(gap > 0)
  {
    gap=gap/3+1;
    int i=gap;
    for(;i<n;i++)
    {
      int end=i-gap;
      int key=a[i];

      while(end>=0 && key<a[end])
      {
        a[end+gap]=a[end];
        end-=gap;
      }
       a[end+gap] = key;
    }
    gap--;
  }
}

void QuickSort(int *a,int left,int right)
{
  if(right-left>1)
  {
    //InsertSort(a+left,right-left+1);
    //int mid=PartSort1(a,left,right);
    //int mid=PartSort2(a,left,right);
    int mid=PartSort3(a,left,right);
    QuickSort(a,left,mid);
    QuickSort(a,mid+1,right);
  }
}

void MergeSort(int *a,int l,int r)
{
  if(l>=r) return ;

  int mid =(l + r)/2;

  MergeSort(a,l,mid),MergeSort(a,mid+1,r);
  int k=0,i=l,j=mid+1,tmp[r-l+1];
  
  while(i<=mid && j<=r)
  {
    if(a[i]<=a[j]) tmp[k++]=a[i++];
    else tmp[k++]=a[j++];
  }

  while(i<=mid) tmp[k++]=a[i++];

  while(j<=r) tmp[k++]=a[j++];
  
  int m,n;
  for(m=l,n=0;m<=r;m++,n++) a[m]=tmp[n];
}

void MergeArr(int* a, int begin1, int end1, int begin2, int end2, int* tmp)
{
    int left = begin1, right = end2;
      int index = begin1;
        while (begin1 <= end1 && begin2 <= end2)
        {
              if (a[begin1] < a[begin2])
                      tmp[index++] = a[begin1++];
                  else
                          tmp[index++] = a[begin2++];
                    
        }

          while (begin1 <= end1)
                tmp[index++] = a[begin1++];

            while (begin2 <= end2)
                  tmp[index++] = a[begin2++];
                int i=left;
              // 把归并好的再tmp的数据在拷贝回到原数组
                for ( ; i <= right; ++i)
                    a[i] = tmp[i];
              
}

void MergeSortNonR(int* a, int n)
{
    int i;
    int* tmp =(int*) malloc(sizeof(int) * n);
    int gap = 1; //每组元素个数
    while (gap < n)
    {
      for(i = 0;i<n;i+=2*gap)
      {
        int begin1=i,end1=i+gap-1;
        int begin2=i+gap,end2 = i+2*gap-1;

        if(begin2 >= n)
          break;

        if(end2 >= n)
          end2=n-1;

        MergeArr(a,begin1,end1,begin2,end2,tmp);
      }
      gap*=2;
    }
  free(tmp);
}
void CountSort(int *array,int n)
{
  int maxValue = array[0];
  int minValue = array[0];
  int i;
  for(i=0;i<n;i++)
  {
    if(array[i] > maxValue)
      maxValue = array[i];

    if(array[i] < minValue)
      minValue = array[i];
  }

  int range = maxValue - minValue + 1;

  int *count=(int *)malloc(range*sizeof(int));
  if(count== NULL)
  {
    assert(0);
    return ;
  }

  memset(count,0,range*sizeof(int));

  for(i=0;i<n;i++)
  {
    count[array[i]-minValue]++;
  }

  int index=0;
  for(i=0;i<range;i++)
  {
    while(count[i])
    {
      array[index++] = i + minValue;
      count[i]--;
    }
  }
  free(count);
}
